package com.sjf.day02.sort;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * @author <huangtang>
 * @since 2021/12/27 14:10
 **/
public class ShellSort {
    public static void main(String[] args) {
        //int[] num ={8,9,1,7,2,3,5,4,6,0};
        int[] num = new int[100000];
        for (int i = 0; i < 100000; i++) {
            num[i] = (int)(Math.random() * 1000000); //生产 0 - 100000的随机数
        }
        long t1 = System.currentTimeMillis();
        shellSort2(num);
        //System.out.println(Arrays.toString(num));
        System.out.println("希尔排序用时："+(System.currentTimeMillis()-t1)); //24ms

    }

    /**
     * 希尔排序--移位法
     * @param num
     */
    public static void shellSort2(int[] num){
        int n = num.length;
        while((n/=2)!=0){
            //从第n个元素，逐个对其所在的组进行插入操作
            for (int i = n; i < num.length; i++) {
                int j = i; //获取第n个元素的下标
                int temp = num[j]; //暂存第n个元素
                if(num[j] < num[j-n]){ //判断第j个元素和一组中的另一个元素j-n的大小，如果小于
                    while(j-n >= 0 && temp < num[j-n] ){
                        //j-n判断是否到达该组中最前面的数
                        //移动
                        num[j] = num[j-n]; //将较大的数 移到 j下标的元素(后移)
                        j -= n; //下标j继续前移，继续判断前面的数
                    }
                    //当退出while循环后，找到了插入的位置
                    num[j] = temp;
                }
            }
        }
    }


    /**
     * 希尔排序--交换法
     * @param num
     */
    public static void shellSort(int[] num){

        int n = num.length;
        int count = 0;
        while((n/= 2)!=0) {
            for (int i = n; i < num.length; i++) {
                for (int j = i - n; j >= 0; j -= n) {
                    if (num[j] > num[j + n]) {
                        swap(num, j, j + n);
                    }
                }
            }
            //System.out.printf("希尔排序第 %d 轮 为：%s  \n",++count,Arrays.toString(num));
        }
        //System.out.println(Arrays.toString(num));

/*
        //第一轮希尔排序
        //第一轮将10个数组分成5组 10/2=5
        for (int i = 5; i < num.length; i++) {
            for (int j = i-5; j >=0; j-=5) {
                //如果当前元素大于加上步长后的元素，则交换
                if(num[j] > num[j+5]){
                    swap(num,j,j+5);
                }
            }
        }
        System.out.printf("第一轮希尔排序 %s \n", Arrays.toString(num)); //[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]

        //第二轮希尔排序
        //第二轮将10个数组分成2组 10/2/2=2
        for (int i = 2; i < num.length; i++) {
            for (int j = i-2; j >= 0; j-=2) {
                //如果当前元素大于加上步长后的元素，则交换
                if(num[j] > num[j+2]){
                    swap(num,j,j+2);
                }
            }
        }
        System.out.printf("第二轮希尔排序 %s \n", Arrays.toString(num));//[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]

        //第二轮希尔排序
        //第二轮将10个数组分成2组 10/2/2/2=1
        for (int i = 1; i < num.length; i++) {
            for (int j = i-1; j >= 0; j-=1) {
                //如果当前元素大于加上步长后的元素，则交换
                if(num[j] > num[j+1]){
                    swap(num,j,j+1);
                }
            }
        }
        System.out.printf("第三轮希尔排序 %s \n", Arrays.toString(num));//[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
*/
    }

    public static void swap(int[] num,int i,int j){
        num [i] = num[i] ^ num[j];
        num [j] = num[i] ^ num[j];
        num [i] = num[i] ^ num[j];
    }
}
